/* Min priority queue backed by a doubly-linked list */

#include <stdlib.h>
#include <autoconf.h>

#include "queue.h"

timer_queue timer_queue_init(int max_capacity) {
    timer_queue q = malloc(sizeof(struct timer_queue));
    q->capacity = max_capacity;
    q->size = 0;
    q->head = NULL;
    return q;
}

void timer_queue_free(timer_queue q) {
    timer_node *ptr = q->head;
    timer_node *next;
    while (ptr) {
        next = ptr->next;
        free(ptr);
        ptr = next;
    }
    free(q);
    return;
}

void timer_queue_insert_after(timer_queue queue, timer_node *dst, timer_node *new) {
    new->prev = dst;
    new->next = dst->next;
    // if (new->next == NULL) queue->tail = new;
    // else dst->next->prev = new;
    dst->next = new;
}

void timer_queue_insert_before(timer_queue queue, timer_node *dst, timer_node *new) {
    new->prev = dst->prev;
    new->next = dst;
    if (dst->prev == NULL)
        queue->head = new;
    else
        dst->prev->next = new;
}

void timer_queue_push_front(timer_queue queue, timer_node *new) {
    if (queue->head == NULL) {
        queue->head = new;
        // queue->tail = new;
        new->next = NULL;
        new->prev = NULL;
    } else {
        timer_queue_insert_before(queue, queue->head, new);
    }
}

// void timer_queue_push_back(

int timer_queue_insert(timer_queue q, timestamp_t key, timer_callback_t cb,
                       void *data, uint32_t *id) {
    timer_node *new = malloc(sizeof(struct timer_node));
    if (!new) return TIMER_OP_OOM;

    if (q->size == q->capacity) return TIMER_OP_FULL;
    q->size++;

    new->key = key;
    new->callback = cb;
    new->data = data;
    new->id = (uint32_t) new;
    *id = (uint32_t) new;

    // Find insertion point
    timer_node *ptr = q->head;
    while (ptr && ptr->next && ptr->key <= key) {
        ptr = ptr->next;
    }

    if (!ptr) {
        // The list was empty. We are the new head.
        timer_queue_push_front(q, new);
    } else if (ptr->key <= key) {
        // we go after ptr - ptr is the last element
        timer_queue_insert_after(q, ptr, new);
    } else {
        // Normal case: We insert ahead of ptr.
        // We could be the new head.
        timer_queue_insert_before(q, ptr, new);
    }
    return TIMER_OP_OK;
}

int timer_queue_min(timer_queue q, timer_node *n) {
    if (q->size < 1) return TIMER_OP_EMPTY;
    *n = *(q->head);
    return TIMER_OP_OK;
}

int timer_queue_min_remove(timer_queue q) {
    if (q->size < 1) return TIMER_OP_EMPTY;
    timer_node *old = q->head;
    q->head = old->next;
    if (q->head) q->head->prev = NULL;
    q->size--;
    free(old);
    return TIMER_OP_OK;
}

int timer_queue_conditional_pop(timer_queue q, timer_node *n, timestamp_t thresh) {
    int err = timer_queue_min(q, n);
    if (err) return err;

    if (n->key <= thresh) {
        err = timer_queue_min_remove(q);
        return err;
    } else {
        return TIMER_OP_COND;
    }
}

int timer_queue_id_remove(timer_queue q, uint32_t id) {
    timer_node *n = (timer_node *) id;
    if (!n->prev) {
        // We are root
        q->head = n->next;
    }

    if (n->next) n->next->prev = n->prev;
    if (n->prev) n->prev->next = n->next;
    free(n);
    q->size--;
    return TIMER_OP_OK;
}

/*
int main (int argc, char** argv) {
    timer_queue q = timer_queue_init(100);
    int i, err;
    uint32_t id;
    for (i = 0; i < 100; i++) {
       err = timer_queue_insert(q, i%15, NULL, NULL, &id);
       if (err) printf("ERROR\n");
    }

    timer_node n;
    timer_queue_min(q, &n);
    printf("The least element of this queue is: %llu\n", n.key);
    printf("The queue has size %d remaining, and %d slots total.\n", q->size, q->capacity);

    err = 0;
    while (!err) {
        err = timer_queue_min(q, &n);
        if (!err) {
            printf("%llu ", n.key);
            err = timer_queue_min_remove(q);
       
        }
    }
    printf("\n");

    printf("Items remaining: %d\n", q->size);

    timer_queue_free(q);
    return 0;
}
*/
